/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM75 编辑距离(一)
 * <a href="https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=295&tqId=2294660&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-11-16
 * Time: 17:15
 */

//动态规划
//本题的另一种思路可以是求出最长公共子序列，然后通过运算直接可以求出最短编辑距离
//细想此题，其实和BM65 最长公共子序列的解题方法一模一样
import java.util.*;

public class Solution {
    public int editDistance (String str1, String str2) {
        //题目中规定：字符串长度满足 1 < n < 1000 ，且字符串中只出现小写英文字母
        int len1 = str1.length();
        int len2 = str2.length();
        //dp[i][j]表示的是示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的最短编辑距离
        //初始条件：dp的第一行和第一列都应初始为dp[0][i] = dp[0][i-1] + 1,dp[i][0] = dp[i-1][0] + 1
        //状态转移：若str1的第i个字符和str2的第j个字符相等，则dp[i][j] = dp[i-1][j-1] + 1
        //        若不等，则dp[i][j]=min(dp[i−1][j−1],min(dp[i−1][j],dp[i][j−1]))+1
        int[][] dp = new int[len1 + 1][len2 + 1];
        //初始化第一行
        for (int i = 1; i <= len2; i++) {
            dp[0][i] = dp[0][i-1] + 1;
        }
        //初始化第一列
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i-1][0] + 1;
        }
        //状态转移
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
                }
            }
        }
        //返回结果
        return dp[len1][len2];
    }
}